edx 课程《Introduction to Probability - The Science of Uncertainty》Unit1 笔记
Unit1 Probability models and axioms
1. Sample Space（样本空间）
样本空间 $\Omega$ 是一次实验所有可能结果的集合。
对于一个样本空间而言，它需要满足的条件是：
Mutually exclusive（互斥性） 也就是说，一次性只可能有一个结果出现
collectively exhaustive（穷尽所有可能） 也就是说，所有的结果都会在这个样本空间里面。
At the “right” granularity 也就是说，我们样本空间的结果应该在适合的“粒度”
这里解释一下第3个条件。
比如，现在的事件是 “掷骰子” 我们的样本空间有两个选择
{数字 、 人头}
和
{数字,下雨 、 数字,晴天、 人头,下雨 人头,晴天}
那么在 “掷骰子” 这个事件中，适合“粒度”的样本空间是 {数字 、 人头}
2. Event（事件） and Probability（概率）
事件是样本空间的一个子集。 当一个实验结束之后，会产生一个结果，这个时候，这个结果就可以看成是事件A发生了。 (A是泛指)
注意，事件A发生的 “可能性” 被我们称为 概率，用符号表示就是 $P(A)$
2.1 概率的三条公理：
Nonnegativity（非负性） 对于样本空间中所有的事件 —— A (A是泛指)，都有 P(A) ≥ 0
Additivity（可列可加性） 即互不相容事件的并集的概率为各事件概率之和，也就是 如果 $A \cap B = \varnothing$ 那么 $P(A \cup B) = P(A) + P(B)$。 更一般地，如果样本空间是有限的，且 $A_1, A_2, …$ 是一系列不相交事件，那么它们的概率和应该满足 $P(A_1 \cup A_2 \cup …) = P(A_1) + P(A_2) + …$
Normalization（规范性） 即整个样本空间的概率是 1 ， 也就是 $P(\Omega) = 1$
通过上面的三条公理，我们可以推出一系列结论：
2.2 概率的一系列推论：
$P(A) \leqq 1$
$P(\varnothing) = 0$
$P(A) + P(A^c) = 1$ 也就是事件 $A$ 和事件 $A$ 的补集的和为1， A的补集 就是符合 $A \cap A^c = \varnothing$ 和 $A \cup A^c = \Omega$ 的事件
上面三个推论比较简单，我们就不写出证明过程了。
如果 $A \subset B$, 那么 $P(A)\leqq P(B)$ ； 证明： 因为 $B = A \cup (B \cap A^c)$ 所以 $P(B) = P(A) + P(B \cap A^c) \geq P(A)$
$P(A \cup B) = P(A) + P(B) - P(A \cap B)$ ； 证明： 设 $a = P(A \cap B^c)$ ， $b = P(A \cap B)$ ， $c = P(B \cap A^c)$ 那么 $P(A \cup B) = a + b + c$ ； 同时 $P(A) + P(B) - P(A \cap B) = (a+b) + (b+c) - b = a + b + c$，所以两者相等。
$P(A \cup B) \leqq P(A) + P(B)$ ； 证明：由公理(1) 可知， $P(A \cap B) \geq 0$ ，再结合推论(5)，可以得证。这一个式子比较重要，我们通常称呼它为 Union Bound
$P(A \cup B \cup C) = P(A) + P(A^c \cap B) + P(A^c \cap B^c \cap C)$
2.3 概率的计算步骤
确定样本空间
确定一个 probability law (概率分布)
确定一个感兴趣的事件
计算…
对于离散、有限数据，我们通常采取的措施是计数； （例子：略）
对于连续数据，我们通常采取的措施是计算面积 （例子：略）
对于离散、无限数据，通常会需要用到一些数列相关的知识。
比如，现在我们有一个实验是扔骰子直到数字向上的事件发生，理论上来说，这个事件发生可能会在第一次、第二次、第三次、 …
所以，上述实验的样本空间是所有正整数的集合。
那么概率分布可以用 $P(n) = \frac{1}{2^n}, \ \ n=1,2,3 …$
现在，我们来证明，这个概率分布是合理的！
$$ \sum_{n=1}^{\infty} \frac{1}{2^n} = \frac{1}{2} \sum_{n=1}^{\infty} \frac{1}{2^n} = \frac{1}{2} \cdot \frac{1}{1 - \frac{1}{2}} = 1 $$
符合我们对概率的定义。
那么接下来，我们来求事件 结果是偶数 的概率。
$$P(outcome \ is \ even) = P({2, 4, 6, …}) \
= P({2} \cup {4} \cup {6} \cup …) = P(2) + P(4) + … \
= \frac{1}{2^2} + \frac{1}{2^4} + \frac{1}{2^6} + … \
= \frac{1}{4} (1 + \frac{1}{4} + \frac{1}{4^2} + …) \
= \frac{1}{4} \cdot \frac{1}{1 - \frac{1}{4}} = \frac{1}{3}$$
一个有趣的现象
对于一个单位面积的矩阵。它的样本空间是整个矩阵的面积。
那么我们是否可以得到如下的式子呢？
$$P(\cup {(x, y) } ) = \sum P( {(x, y) } ) \ \ (*)$$
我们先假设可以得到这样的式子，那么很显然左边会有 $P(\cup {(x, y) } = P(\Omega) = 1$ ，而右边却又是 $P( {(x, y) } ) = 0$, 则 $\sum P( {(x, y) } ) = 0$ ,这样会出现一个悖论 $1 = 0$ ！！
为什么会这样呢？原因出在了我们刚才的式子 $()$ 上，等式 $()$ 真的成立么？
不成立！！ 因为这样划分得到的结果并不是一个 sequence。
这里是我的个人理解：因为我们如果把一个单位面积的矩阵，确实可以用无穷多个点来表示，但是这无穷多个点是不可数的！！只有当我们对无限但可数个元素进行求和，才能满足可列可加性。
2.4 概率的一些解释
狭义上来讲，概率 可以看成是数学的一个分支。
在这个分支中，我们通常用事件 $A$ 发生的频率表示概率。
但是，不够完整，比如如果现在事件 $A$ 是 “我们上课会迟到”
那，我们没办法用频率表示…
这时候，我们会引申出另外一个含义，那就是 信念。刚才的列子 $P(“我们上课会迟到”) = 0.7$ 就是我们对上课迟到这件事发生的信念是 0.7
我个人的理解是，概率就是我们用来描述不确定性事件的工具。具体关系图，如下图所示：
3. 数学背景回顾
3.1 Sets（集合）
集合的定义： A collection of distinct elements
集合有两种： 有限集 和 无限集。 比如 ${ a, b, c, d}$ 就是有限集； $R: real number$ 就是无限集
集合的元素跟集合的关系有 $x \in S$ 和 $x \notin S$
一个比较常见的集合例子： $x \in R : cos(x) > \frac{1}{2}$ [有范围、有限制] 是比较常见的集合。
全集的定义：a universal set is a set which contains all elements, including itself. 我们通常用 $\Omega$ 表示全集
补集的定义： $x \in S^c \ \ if \ \ x \in \Omega \ \ and \ \ x \notin S$
空集的定义： the empty set or null set is the unique set having no elements
子集的定义和性质：a set A is a subset of a set B, if A is “contained” inside B, that is, all elements of A are also elements of B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment. A is a subset of B may also be expressed as B includes A; or A is included in B.
$S$ 是 $T$ 的子集用数学公式表达就是 $S \subset T: \ \ x \in S \Rightarrow x \in T$
并集的定义： $x \in S \cup T \Leftrightarrow x \in S \ \ or \ \ x \in T$
交集的定义： $x \in S \cap T \Leftrightarrow x \in S \ \ and \ \ x \in T$
交集和并集的定义可以推广到无穷多个集合上。
集合的一些性质
(1) $\Omega^c = \emptyset$
(2) $S \cup T = T \cup S$
(3) $S \cup (T \cup U) = (S \cup T) \cup U$
(4) $S \cap (T \cup U) = (S \cap T) \cup (S \cap U)$
(5) $S \cup (T \cap U) = (S \cup T) \cap (S \cup U)$
(6) ${(S^c)}^c = S$
(7) $S \cap S^c = \emptyset$
(8) $S \cup \Omega = \Omega$
(9) $S \cap \Omega = S$
De Morgan’s law
$${(\bigcup \limits_n S_n)}^c = \bigcap \limits_n S_n^c$$
$${(\bigcap \limits_n S_n)}^c = \bigcup \limits_n S_n^c$$
解释一下：我们用两个集合来进行表示
对于 ${(S \cap T)}^c = S^c \cup T^c$ 来说，我们可以证明
$$x \in {(S \cap T)}^c \Leftrightarrow x \notin S \cap T \
\Leftrightarrow x \notin S \ \ or \ \ x \notin T \
\Leftrightarrow x \in S^c \ \ or \ \ x \in T^c \
x \in S^c \cup T^c$$
对于 ${(S \cup T)}^c = S^c \cap T^c$ 来说，我们可以证明
$$x \in {(S \cup T)}^c \Leftrightarrow x \notin S \cup T \
\Leftrightarrow x \notin S \ \ and \ \ x \notin T \
\Leftrightarrow x \in S^c \ \ and \ \ x \in T^c \
\Leftrightarrow x \in S^c \cap T^c$$
3.2 Sequences（数列） and their limits（极限）
数列的定义： 对于一列有序的数 $a_1$, $a_2$, $a_3$, $…$ ，然后简记为 ${ a_i }$ 那么 ${ a_i }$ 就被我们称为数列。数列中的每一个元素，被我们称为 “项”。
对于数列来说，它的索引是 $i \in N = {1, 2, 3, …}$， 但是它的 “项” 没有固定的值，可以为任意值。
所以，我们可以把一个数列理解为一个函数。这个函数是 $f: N \Rightarrow S$，且 $f(i) = a_i$
那么什么是数列的极限呢？
对于一个数列来说，它的极限是
$$if \ \ have \ \ real \ \ number \ \ a \ \ for \ \ any \ \ \epsilon > 0 , \ \ there \ \ exists \ \ N, \ \ such \ \ that \
if \ \ i \geq N, \ \ then \ \ |a_i - a| < \epsilon$$
这时候，我们就称 $a$ 为数列 $a_i$ 的极限。
数列何时收敛？(sequence converge)
两个证明方式：
对于所有的 $i$ 来说，如果 $a_i < a_{i+1}$ 那么：
- 数列发散 (也就是收敛到无穷大)
- 数列收敛到某个实数 $a$
对于所有的 $i$ 来说，如果 $|a_i - a| \leq b_i$ 成立，且 $b_i \to 0$， 那么 $a_i \to a$
无穷级数（infinite series）
无穷级数的定义： 对于一个数列，我们有 $\sum \limits_{i=1}^{\infty} a_i = \lim \limits_{n \to \infty} \sum \limits_{i=1}^{n} a_i$ 当且仅当极限存在的时候成立。
什么时候极限存在呢？
如果 $a_i \geq 0$， 极限存在。 （因为这个时候，它是一个单调级数）
如果所有的 $a_i$ 不一定有着相同的符号
- 极限不存在
- 极限可能存在，但是当我们通过不同的顺序来加的时候，结果可能不同（举个例子就是：奇数顺序和偶数顺序得到的结果是不同的）
- 事实上 如果我们可以证明 $\sum \limits_{i=1}^{\infty} |a_i| < \infty$ 那么极限存在。
等比级数
$$S = \sum \limits_{i=0}^{\infty} |\alpha_i| = 1 + \alpha + \alpha^2 + … \ \ \ \ \ \ \ \ |\alpha| < 1$$
那么 $S$ 等于多少呢？
很简单，我们可以通过如下式子证得：
$$(1 - \alpha) (1 + \alpha + … + \alpha^n) = 1 - \alpha^{n+1} \
n \to \infty \
(1 - \alpha) S = 1 \
S = \frac{1}{1 - \alpha}$$
多指标级数
只要我们能保证 $\sum |a_{ij}| < \infty$， 那么我们用什么样的顺序进行加操作都是OK的。
所以
$$\sum \limits_{i \geq 1, j \geq 1} a_{ij} = \sum \limits_{i=0}^{\infty} ( \sum \limits_{j=0}^{\infty} a_{ij}) = \sum \limits_{j=0}^{\infty} ( \sum \limits_{i=0}^{\infty} a_{ij})$$
又比如：
$$\sum \limits_{(i, j) : j \leq i} a_{ij} = \sum \limits_{i=1}^{\infty} ( \sum \limits_{j=1}^{i} a_{ij}) = \sum \limits_{i=j}^{\infty} ( \sum \limits_{j=1}^{\infty} a_{ij})$$
3.3 可数集合和不可数集合
可数的定义： can be put in 1-1 correspondence with positive integers.
也就是说对于集合 $\Omega$ 来说，我们可以对 $\Omega$ 中的每一个元素都给定一个下标，使得 ${ a_1, a_2, … } = \Omega$
比如 正整数（ $1, 2, 3, …$ ）就是可数的、整数（ $0, 1, -1, 2, -2, …$ ）也是可数的、成对的整数（ $a_{ij}$ ）也是可数的、有理数 $q$ 且 $0 < q < 1$ （ $\frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, …$ ）也是可数的
不可数的定义： not countable
比如区间 $[0, 1]$ 就是不可数的。再比如 实数集、平面 都是不可数的。
证明：实数是不可数的。
对于区间 $[0, 1]$ 来说，我们假设它是可数的。那么 $[0, 1]$ 中的所有元素可以写成集合 ${ x_1, x_2, …}$
现在，假设 $x_1 = 0.A_{11} A_{12} A_{13} …$ , $x_2 = 0.A_{21} A_{22} A_{23} …$, $x_3 = 0.A_{31} A_{32} A_{33} …$ 然后我们选择一个不同于 $A_{11}$ 的元素 $A_1$ 和不同于 $A_{22}$ 的元素 $A_2$ 和不同于 $A_{33}$ 的元素 $A_3$ … 将这些元素组合在一起形成了一个新的数 $\hat{x} = 0.A_1A_2A_3A_4…$ 那么很显然 $\hat{x}$ 不等于 $x_1$, 也不等于 $x_2$, 也不等于 $x_3$, 也不等于 $x_4$, … 它跟集合中所有项都不相等，但是 $\hat{x}$ 又在 $[0,1]$ 之间，那么结论跟假设冲突，则假设是错误的，所以区间 $[0, 1]$ 不可数。
4. 作业
- 证明 ${\bf P}\Big((A \cap B^ c) \cup (A^ c \cap B)\Big)={\bf P}(A)+{\bf P}(B)-2\cdot {\bf P}(A\cap B)$
证明如下：
因为 $(A \cap B^c) \cap (A^c \cap B) = (A \cap A^c) \cap (B^c \cap B) = \varnothing$
那么 ${\bf P}\Big((A \cap B^ c) \cup (A^ c \cap B)\Big) = {\bf P}(A \cap B^ c) + {\bf P}(A^ c \cap B)$
其中 ${\bf P}(A \cap B^ c) = {\bf P}(A) - {\bf P}(A \cap B)$, ${\bf P}(A^ c \cap B) = {\bf P}(B) - {\bf P}(A \cap B)$
所以${\bf P}\Big((A \cap B^ c) \cup (A^ c \cap B)\Big) = {\bf P}(A) + {\bf P}(B) - 2 \cdot {\bf P}(A \cap B)$
- Geniuses and chocolates. Out of the students in a class, 60% are geniuses, 70% love chocolate, and 40% fall into both categories. Determine the probability that a randomly selected student is neither a genius nor a chocolate lover.
解：
设事件 A 为 “student is genius”, 事件 B 为 “student love chocolate”
由题意可得 ${\bf P}(A) = 0.6$, ${\bf P}(B) = 0.7$, ${\bf P}(A \cap B) = 0.4$
所以，结果为 ${\bf P}(A^c \cap B^c) = {\bf P}( (A \cup B)^c ) = 1 - ( {\bf P}(A) + {\bf P}(B) - {\bf P}(A \cap B)) = 1 - (0.6 + 0.7 - 0.4) = 0.1$
- Uniform probabilities on a square. Romeo and Juliet have a date at a given time, and each will arrive at the meeting place with a delay between 0 and 1 hour, with all pairs of delays being “equally likely,” that is, according to a uniform probability law on the unit square. The first to arrive will wait for 15 minutes and will leave if the other has not arrived. What is the probability that they will meet?
解：
我们设 $i$ 表示 Romeo 到达的时间，所以 $0 < i < 60$，设 $j$ 表示 Juliet 达到的时间，所以 $i - 15 \leq j \leq i + 15$ 为此，我们可依据上述的表达式在一个二维平面上画出图像来。
黑色平面的部分就是 Romeo 和 Juliet 能够碰到的时间。
所以，我们可以算出黑色部分的面积是 $2 \cdot \frac{1}{2} \cdot \frac{3}{4} \cdot \frac{3}{4} = \frac{7}{16}$
所以，它们能够成功约会的概率是 $\frac{7}{16}$
Bonferroni’s inequality.
(a) Prove that for any two events $A1$ and $A2$, we have
$${\bf P}(A_1 \cap A_2) \geq {\bf P}(A_1) + {\bf P}(A_2)-1.$$(b) Generalize to the case of n events $A1,A2,…,An$, by showing that
$${\bf P}(A_1 \cap A_2 \cap \cdots \cap A_ n)\geq {\bf P}(A_1)+{\bf P}(A_2)+\cdots +{\bf P}(A_ n)-(n-1).$$
解：(a)
因为 ${\bf P}(A_1 \cup A_2) = {\bf P}(A_1) + {\bf P}(A_2) - {\bf P}(A_1 \cap A_2)$
所以 ${\bf P}(A_1 \cap A_2) = {\bf P}(A_1) + {\bf P}(A_2) - {\bf P}(A_1 \cup A_2)$
又因为 ${\bf P}(A_1 \cup A_2) \leq 1$
所以 ${\bf P}(A_1 \cap A_2) \geq {\bf P}(A_1) + {\bf P}(A_2) - 1$
所以，得证。
解：(b)
因为 ${\bf P} ({(A_1 \cap A_2)}^c) = {\bf P}(A_1^c \cup A_2^c) \leq {\bf P}(A_1^c) + {\bf P}(A_2^c)$
所以 $1 - {\bf P}(A_1 \cap A_2) \leq 1 - {\bf P}(A_1) + 1 - {\bf P}(A_2)$
所以 ${\bf P}(A_1 \cap A_2) \geq {\bf P}(A_1) + {\bf P}(A_2) - 1$
类似的情况可以推广到 $A_n$
因为 ${\bf P}({(A_1 \cap A_2 \cap … \cap A_n)}^c) = {\bf P}(A_1^c \cup … \cup A_n^c) \leq {\bf P}(A_1^c) + … + {\bf P}(A_n^c)$
所以利用 ${\bf P}(A^c) = 1 - {\bf P}(a)$ 带入上式可以得到结果。